home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / graphic / pbmpl91d.zip / PBMPLUS / NEWSRC / PPMQVGA.C < prev   
C/C++ Source or Header  |  1993-01-08  |  14KB  |  508 lines
  1. /*
  2.  *  ppmqvga.c - quantize the colors in a pixmap down to a VGA
  3.  *    (256 colors, 6 bits per pixel)
  4.  *
  5.  *  original by Lyle Rains (lrains@netcom.com) as ppmq256 and ppmq256fs
  6.  *  combined, commented, and enhanced by Bill Davidsen (davidsen@crd.ge.com)
  7. */
  8.  
  9. #define DUMPCOLORS 0
  10. #define DUMPERRORS 0
  11.  
  12. #include <stdio.h>
  13. #include <math.h>
  14. #include <malloc.h>
  15. #include "ppm.h"
  16. #ifdef SYSV
  17. #include <string.h>
  18. #define srandom srand
  19. #define random rand
  20. #else /*SYSV*/
  21. #include <strings.h>
  22. #define strchr index
  23. #define strrchr rindex
  24. #endif /*SYSV*/
  25.  
  26. #define min(a,b) ((a) < (b) ? (a) : (b))
  27. #define max(a,b) ((a) > (b) ? (a) : (b))
  28.  
  29. #define RED_BITS   5
  30. #define GREEN_BITS 6
  31. #define BLUE_BITS  5
  32.  
  33. #define MAX_RED    (1 << RED_BITS)
  34. #define MAX_GREEN  (1 << GREEN_BITS)
  35. #define MAX_BLUE   (1 << BLUE_BITS)
  36.  
  37. #define MAXWEIGHT  128
  38. #define STDWEIGHT_DIV  (2 << 8)
  39. #define STDWEIGHT_MUL  (2 << 10)
  40. #define COLORS     256
  41. #define GAIN       4
  42.  
  43. #define BARGRAPH     "__________\b\b\b\b\b\b\b\b\b\b"
  44. #define BARGRAPHLEN  10
  45.  
  46. int color_cube[MAX_RED][MAX_GREEN][MAX_BLUE];
  47.  
  48. unsigned char clut[COLORS][4];
  49. int erropt[COLORS][4];
  50. enum { red, green, blue, count };
  51. int clutx;
  52.  
  53. int weight_convert[MAXWEIGHT];
  54. int total_weight, cum_weight[MAX_GREEN];
  55. int rep_weight, rep_threshold;
  56. int r, g, b, dr, dg, db;
  57. int dither = 0, verbose = 1;
  58.  
  59. pixval maxval;
  60.  
  61. /*
  62. ** 3-D error diffusion dither routine for points in the color cube; used to
  63. ** select the representative colors.
  64. */
  65. diffuse()
  66. {
  67.   int _7_32nds, _3_32nds, _1_16th;
  68.  
  69.   if (clutx < COLORS) {
  70.     if (color_cube[r][g][b] > rep_threshold) {
  71.  
  72.       clut[clutx][red]   = ((2 * r + 1) * (maxval + 1)) / (2 * MAX_RED);
  73.       clut[clutx][green] = ((2 * g + 1) * (maxval + 1)) / (2 * MAX_GREEN);
  74.       clut[clutx][blue]  = ((2 * b + 1) * (maxval + 1)) / (2 * MAX_BLUE);
  75. #if DUMPCOLORS
  76.       if (verbose > 2) {
  77.         /* Dump new color */
  78.         if ((clutx & 3) == 0) {
  79.           fprintf(stderr, "\n  %3d (%2d): ", clutx, rep_threshold);
  80.         }
  81.         fprintf(stderr,
  82.       " (%03d,%03d,%03d)", clut[clutx][red],
  83.       clut[clutx][green], clut[clutx][blue]
  84.     );
  85.       }
  86. #endif
  87.       ++clutx;
  88.       color_cube[r][g][b] -= rep_weight;
  89.     }
  90.     _7_32nds = (7 * color_cube[r][g][b]) / 32;
  91.     _3_32nds = (3 * color_cube[r][g][b]) / 32;
  92.     _1_16th = color_cube[r][g][b] - 3 * (_7_32nds + _3_32nds);
  93.     color_cube[ r  ][ g  ][ b  ]  = 0;
  94.     /* spread error evenly in color space. */
  95.     color_cube[ r  ][ g  ][b+db] += _7_32nds;
  96.     color_cube[ r  ][g+dg][ b  ] += _7_32nds;
  97.     color_cube[r+dr][ g  ][ b  ] += _7_32nds;
  98.     color_cube[ r  ][g+dg][b+db] += _3_32nds;
  99.     color_cube[r+dr][ g  ][b+db] += _3_32nds;
  100.     color_cube[r+dr][g+dg][ b  ] += _3_32nds;
  101.     color_cube[r+dr][g+dg][b+db] += _1_16th;
  102.     /* Conserve the error at edges if possible (which it is, except the last pixel) */
  103.     if (color_cube[r][g][b] != 0) {
  104.       if      (dg != 0)   color_cube[r][g+dg][b] += color_cube[r][g][b];
  105.       else if (dr != 0)   color_cube[r+dr][g][b] += color_cube[r][g][b];
  106.       else if (db != 0)   color_cube[r][g][b+db] += color_cube[r][g][b];
  107.       else fprintf(stderr, "\nlost error term\n");
  108.     }
  109.   }
  110.   color_cube[r][g][b] = -1;
  111. }
  112.  
  113. /*
  114. ** Find representative color nearest to requested color.  Check color cube
  115. ** for a cached color index.  If not cached, compute nearest and cache result.
  116. */
  117. int nearest_color(pP)
  118.   register pixel *pP;
  119. {
  120.   register unsigned char *test;
  121.   register unsigned i;
  122.   unsigned long min_dist_sqd, dist_sqd;
  123.   int nearest;
  124.   int *cache;
  125.   int r, g, b;
  126.  
  127.   r = ((int)(PPM_GETR(*pP)));
  128.   g = ((int)(PPM_GETG(*pP)));
  129.   b = ((int)(PPM_GETB(*pP)));
  130.   if ((i = maxval + 1) == 256) {
  131.     cache = &(color_cube[r>>(8-RED_BITS)][g>>(8-GREEN_BITS)][b>>(8-BLUE_BITS)]);
  132.   }
  133.   else {
  134.     cache = &(color_cube[(r<<RED_BITS)/i][(g<<GREEN_BITS)/i][(b<<BLUE_BITS)/i]);
  135.   }
  136.   if (*cache >= 0) return *cache;
  137.   min_dist_sqd = ~0;
  138.   for (i = 0; i < COLORS; ++i) {
  139.     test = clut[i];
  140.     dist_sqd = 3 * (r - test[red])   * (r - test[red])
  141.              + 4 * (g - test[green]) * (g - test[green])
  142.              + 2 * (b - test[blue])  * (b - test[blue]);
  143.     if (dist_sqd < min_dist_sqd) {
  144.       nearest = i;
  145.       min_dist_sqd = dist_sqd;
  146.     }
  147.   }
  148.   return (*cache = nearest);
  149. }
  150.  
  151.  
  152. /* Errors are carried at FS_SCALE times actual size for accuracy */
  153. #define _7x16ths(x)   ((7 * (x)) / 16)
  154. #define _5x16ths(x)   ((5 * (x)) / 16)
  155. #define _3x16ths(x)   ((3 * (x)) / 16)
  156. #define _1x16th(x)    ((x) / 16)
  157. #define NEXT(line)    (!(line))
  158. #define FS_SCALE      1024
  159.  
  160. typedef int fs_err_array[2][3];
  161.  
  162. void fs_diffuse (fs_err, line, color, err)
  163.   fs_err_array *fs_err;
  164.   int line, color;
  165.   int err;
  166. {
  167.   fs_err[1] [line]       [color] += _7x16ths(err);
  168.   fs_err[-1][NEXT(line)] [color] += _3x16ths(err);
  169.   fs_err[0] [NEXT(line)] [color] += _5x16ths(err);
  170.   fs_err[1] [NEXT(line)] [color]  = _1x16th(err); /* straight assignment */
  171. }
  172.  
  173. void main(argc, argv)
  174.   int argc;
  175.   char *argv[];
  176. {
  177.   FILE *ifd;
  178.   pixel **pixels;
  179.   register pixel *pP;
  180.   int rows, cols, row;
  181.   register int col;
  182.   int limitcol;
  183.   int i, j, k;
  184.   char *ccP;
  185.   int *errP;
  186.   unsigned char *clutP;
  187.   int nearest;
  188.   fs_err_array *fs_err_lines, *fs_err;
  189.   int fs_line = 0;
  190.   char *usage = "[ppmfile]";
  191.   char *pm_progname;
  192.   /* getopt stuff */
  193.   extern int optind;
  194.   extern char *optarg;
  195.  
  196.   /* option parsing */
  197.   while ((i = getopt(argc, argv, "dvq")) >= 0) {
  198.     switch (i) {
  199.     case 'd': /* dither */
  200.       dither = 1; break;
  201.     case 'v': /* verbose */
  202.       ++verbose;
  203.       break;
  204.     case 'q': /* quiet */
  205.       verbose = 0; break;
  206.     }
  207.   }
  208.  
  209.   if ((pm_progname = strrchr(argv[0], '/')) != NULL) ++pm_progname;
  210.   else pm_progname = argv[0];
  211.  
  212.   if ((argc - optind) > 1) pm_usage( usage );
  213.  
  214.   if ((argc - optind) == 1) ifd = pm_openr( argv[optind] );
  215.   else ifd = stdin;
  216.  
  217.   /*
  218.   ** Step 0: read in the image.
  219.   */
  220.   pixels = ppm_readppm( ifd, &cols, &rows, &maxval );
  221.   pm_close( ifd );
  222.  
  223.   /*
  224.   ** Step 1: catalog the colors into a color cube.
  225.   */
  226.   if (verbose) {
  227.     fprintf( stderr, "%s: building color tables %s", pm_progname, BARGRAPH);
  228.     j = (i = rows / BARGRAPHLEN) / 2;
  229.   }
  230.  
  231.   /* Count all occurances of each color */
  232.   for (row = 0; row < rows; ++row) {
  233.  
  234.     if (verbose) {
  235.       if (row > j) {
  236.         putc('*', stderr);
  237.         j += i;
  238.       }
  239.     }
  240.  
  241.     if (maxval == 255) {
  242.       for (col = 0, pP = pixels[row]; col < cols; ++col, ++pP) {
  243.         ++(color_cube[PPM_GETR(*pP) / (256 / MAX_RED)]
  244.                      [PPM_GETG(*pP) / (256 / MAX_GREEN)]
  245.                      [PPM_GETB(*pP) / (256 / MAX_BLUE)]
  246.         );
  247.       }
  248.     }
  249.     else {
  250.       for (col = 0, pP = pixels[row]; col < cols; ++col, ++pP) {
  251.         r = (PPM_GETR(*pP) * MAX_RED)  / (maxval + 1);
  252.         g = (PPM_GETG(*pP) * MAX_GREEN)/ (maxval + 1);
  253.         b = (PPM_GETB(*pP) * MAX_BLUE) / (maxval + 1);
  254.         ++(color_cube[r][g][b]);
  255.       }
  256.     }
  257.   }
  258.  
  259.   /*
  260.   ** Step 2: Determine weight of each color and the weight of a representative color.
  261.   */
  262.   /* Initialize logarithmic weighing table */
  263.   for (i = 2; i < MAXWEIGHT; ++i) {
  264.     weight_convert[i] = (int) (100.0 * log((double)(i)));
  265.   }
  266.  
  267.   k = rows * cols;
  268.   if ((k /= STDWEIGHT_DIV) == 0) k = 1;
  269.   total_weight = i = 0;
  270.   for (g = 0; g < MAX_GREEN; ++g) {
  271.     for (r = 0; r < MAX_RED; ++r) {
  272.       for (b = 0; b < MAX_BLUE; ++b) {
  273.         register int weight;
  274.         /* Normalize the weights, independent of picture size. */
  275.         weight = color_cube[r][g][b] * STDWEIGHT_MUL;
  276.         weight /= k;
  277.         if (weight) ++i;
  278.         if (weight >= MAXWEIGHT) weight = MAXWEIGHT - 1;
  279.         total_weight += (color_cube[r][g][b] = weight_convert[weight]);
  280.       }
  281.     }
  282.     cum_weight[g] = total_weight;
  283.   }
  284.   rep_weight = total_weight / COLORS;
  285.  
  286.   if (verbose) {
  287.     putc('\n', stderr);
  288.     if (verbose > 1) {
  289.       fprintf(stderr, "  found %d colors with total weight %d\n",
  290.         i, total_weight);
  291.       fprintf(stderr, "  avg weight for colors used  = %7.2f\n